package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-15 01:25
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode sortLast = head, cur = head.next;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while (cur != null) {
            if (cur.val >= sortLast.val) {
                sortLast = cur;
            } else {
                ListNode pre = dummy;
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                sortLast.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = sortLast.next;
        }
        return dummy.next;
    }
}
